package com.springboot.java.design.search;


/**
 *  二分查找
 */
public class MiddleSearch {

    public static void main(String[] args) {

        int [] a = {0,1,2,3,4,5,6,7,8,8,8,9,10,11};

//        System.out.println(a[middleSearchWithForEach(a, 9)]);
//        System.out.println(a[middleSearchWithRecursion(a, 9, 0, a.length-1)]);
        System.out.println(middleSearchFirst(a, 8));
        System.out.println(middleSearchLast(a, 8));
        System.out.println(middleSearchGFirst(a, 8));
        System.out.println(middleSearchLFirst(a, 8));
    }

    /**
     *   使用循环方式实现
     * @param a 要查找的数组
     * @return  返回元素的索引
     */
    public static int middleSearchWithForEach(int[] a, int target){

        // 索引
        int start = 0;
        int end = a.length-1;

        while (start <= end){
            int mid  = start + ((end - start) >> 1);
            if(a[mid] < target){
                start = mid + 1;
            }else if(a[mid] > target){
                end = target -1;
            }else {
                return mid;
            }
        }

        return -1;
    }



    /**
     *   使用递归方式实现
     * @param a 要查找的数组
     * @return  返回元素的索引
     */
    public static int middleSearchWithRecursion(int[] a, int target, int start, int end){

        if(start > end){
            return -1;
        }

        int mid = start + ((end - start) >> 1);
        if (a[mid] < target) {
            return middleSearchWithRecursion(a, target, mid + 1, end);
        } else if (a[mid] > target) {
            return middleSearchWithRecursion(a, target, start, target - 1);
        } else {
            return mid;
        }
    }


    /**
     *   查询第一个等于给定元素的索引
     * @param a 要查找的数组
     * @return  返回元素的索引
     */
    public static int middleSearchFirst(int[] a, int target){

        // 索引
        int start = 0;
        int end = a.length-1;

        while (start <= end){
            int mid  = start + ((end - start) >> 1);
            if(a[mid] < target){
                start = mid + 1;
            }else if(a[mid] > target){
                end = target -1;
            }else {
                if(mid == 0 || a[mid -1 ] != target){
                    return mid;
                }
                end = mid - 1;
            }
        }

        return -1;
    }

    /**
     *   查询最后一个等于给定元素的索引
     * @param a 要查找的数组
     * @return  返回元素的索引
     */
    public static int middleSearchLast(int[] a, int target){

        // 索引
        int start = 0;
        int end = a.length-1;

        while (start <= end){
            int mid  = start + ((end - start) >> 1);
            if(a[mid] < target){
                start = mid + 1;
            }else if(a[mid] > target){
                end = target -1;
            }else {
                if(mid == a.length-1 || a[mid + 1] != target){
                    return mid;
                }
                start = mid + 1;
            }
        }

        return -1;
    }


    /**
     *   查询第一个大于给定元素的索引
     * @param a 要查找的数组
     * @return  返回元素的索引
     */
    public static int middleSearchGFirst(int[] a, int target){

        // 索引
        int start = 0;
        int end = a.length-1;

        while (start <= end){
            int mid  = start + ((end - start) >> 1);
            if(a[mid] < target){
                start = mid + 1;
            }else if(a[mid] >= target){
                end = target -1;
            }else {
                // a[mid] == target
                if(a[mid + 1] > target){
                    return mid+1;
                }
                start = mid + 1;
            }
        }

        return -1;
    }

    /**
     *   查询第一个大于给定元素的索引
     * @param a 要查找的数组
     * @return  返回元素的索引
     */
    public static int middleSearchLFirst(int[] a, int target){

        // 索引
        int start = 0;
        int end = a.length-1;

        while (start <= end){
            int mid  = start + ((end - start) >> 1);
            if(a[mid] < target){
                start = mid + 1;
            }else if(a[mid] > target){
                end = target -1;
            }else {
                // a[mid] == target
                if(a[mid - 1] < target){
                    return mid-1;
                }
                end = mid - 1;
            }
        }

        return -1;
    }


}
